import java.util.*;

public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            while (a-- > 0) {
                int n = scanner.nextInt();
                int m = scanner.nextInt();
                int p = scanner.nextInt();
                System.out.println(mod(n,m,p));
            }
        }
    }

    public static long mod(int a, int b, int m) {//快速幂取模
        long ans = 1;
        for (int i = 1; i <= b; i++) {
            ans = ans * a % m;
        }
        return ans;
    }
}